/*
 * @lc app=leetcode.cn id=322 lang=typescript
 *
 * [322] 零钱兑换
 */

// @lc code=start
function coinChange(coins: number[], amount: number): number {
  // dp[i]表示凑满i的金额需要最少的硬币数量
  // 因为会出现不可能凑出的结果，会有不可达状态
  const dp = new Array(amount + 1).fill(-1);
  // 初始化
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (let c of coins) {
      // 当前总金额没硬币金额大
      if (i < c) continue;
      // 没法和当前硬币凑成组合
      if (dp[i - c] === -1) continue;
      // 状态转移
      if (dp[i] === -1 || dp[i] > dp[i - c] + 1) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }

  return dp[amount];
}
// @lc code=end
